Wu's method of characteristic set

Wenjun Wu's method is an algorithm for solving multivariate polynomial equations introduced in the late 1970s by the Chinese mathematician Wen-Tsun Wu. This method is based on the mathematical concept of characteristic set introduced in the late 1940s by J.F. Ritt. It is fully independent of Gröbner basis method, introduced by Bruno Buchberger (1965), even if Gröbner bases may be used to compute characteristic sets [1].

Wu's method is powerful for mechanical theorem proving in elementary geometry, and provides a complete decision process for certain classes of problem. It has been used in research in his laboratory (KLMM, Key Laboratory of Mathematics Mechanization in Chinese Academy of Science) and around the world. The main trends of research on Wu's method concern systems of polynomial equations of positive dimension and differential algebra where Ritt's results have been made effective [2][3]. Wu's method has been applied in various scientific fields, like biology, computer vision, robot kinematics and especially automatic proofs in geometry[4]

Contents

Informal description

Wu's method uses polynomial division to solve problems of the form:

\forall x, y, z, \dots I(x, y, z, \dots) \implies f(x, y, z, \dots) \,

where f is a polynomial equation and I is a conjunction of polynomial equations. The algorithm is complete for such problems over the complex domain.

The core idea of the algorithm is that you can divide one polynomial by another to give a remainder. Repeated division results in either the remainder vanishing (in which case the I implies f statement is true), or an irreducible remainder is left behind (in which case the statement is false).

More specifically, for an ideal I in the ring k[x1, ..., xn] over a field k, a (Ritt) characteristic set C of I is composed of a set of polynomials in I, which is in triangular shape: polynomials in C have distinct main variables (see the formal definition below). Given a characteristic set C of I, one can decide if a polynomial f is zero modulo I. That is, the membership test is checkable for I, provided a characteristic set of I.

Ritt characteristic set

A Ritt characteristic set is a finite set of polynomials in triangular form of an ideal. This triangular set satisfies certain minimal condition with respect to the Ritt ordering, and it preserves many interesting geometrical properties of the ideal. However it may not be its system of generators.

Let R be the multivariate polynomial ring k[x1, ..., xn] over a field k. The variables are ordered linearly according to their subscript: x1 < ... < xn. For a non-constant polynomial p in R, the greatest variable effectively presenting in p, called main variable or class, plays a particular role: p can be naturally regarded as a univariate polynomial in its main variable xk with coefficients in k[x1, ..., xk−1]. The degree of p as a univariate polynomial in its main variable is also called its main degree.

A set T of non-constant polynomials is called a triangular set if all polynomials in T have dinstinct main variables. This generalizes triangular systems of linear equations in a natural way.

For two non-constant polynomials p and q, we say p is smaller than q with respect to Ritt ordering and written as p <r q, if one of the following assertions holds:

(1) the main variable of p is smaller than the main variable of q, that is, mvar(p) < mvar(q),
(2) p and q have the same main variable, and the main degree of p is less than the main degree of q, that is, mvar(p) = mvar(q) and mdeg(p) < mdeg(q).

In this way, (k[x1, ..., xn],<r) forms a well partial order. However, the Ritt ordering is not a total order: there exist polynomials p and q such that neither p <r q nor p r q. In this case, we say that p and q are not comparable. Note that the Ritt ordering is comparing the rank of p and q. The rank, denotey by rank(p), of a non-constant polynomial p is defined to be a power of its main variable: mvar(p)mdeg(p) and ranks are compared by comparing first the variables and then, in case of equality of the variables, the degrees.

A crucial generalization on Ritt ordering is to compare triangular sets. Let T = { t1, ..., tu} and S = { s1, ..., sv} be two triangular sets such that polynomials in T and S are sorted increasingly according to their main variables. We say T is smaller than U w.r.t. Ritt ordering if one of the following assertions holds

(1) there exists k ≤ min(u, v) such that rank(ti) = rank(si) for 1 ≤ i < k and tk <r sk,
(2) u > v and rank(ti) = rank(si) for 1 ≤ i ≤ v.

Also, there exists incomparable triangular sets w.r.t Ritt ordering.

Let I be a non-zero ideal of k[x1, ..., xn]. A subset T of I is a Ritt characteristic set of I if one of the following conditions holds:

(1) T consists of a single nonzero constant of k,
(2) T is a triangular set and T is minimal w.r.t Ritt ordering in the set of all fine triangular sets contained in I.

A polynomial ideal may possess (infinitely) many characteristic sets, since Ritt ordering is a partial order.

Wu characteristic set

The Ritt–Wu process, first devised by Ritt, subsequently modified by Wu, computes not a Ritt characteristic but an extended one, called Wu characteristic set or ascending chain.

A non-empty subset T of the ideal <F> generated by F is a Wu characteristic set of F if one of the following condition holds

(1) T = {a} with a being a nonzero constant,
(2) T is a triangular set and there exists a subset G of <F> such that <F> = <G> and every polynomial in G is pseudo-reduced to zero with respect to T.

Note that Wu characteristic set is defined to the set F of polynomials, rather to the ideal <F> generated by F. Also it can be shown that a Ritt characteristic set T of <F> is a Wu characteristic set of F. Wu characteristic sets can be computed by Wu's algorithm CHRST-REM, which only requires pseudo-remainder computations and no factorizations are needed.

Wu's characteristic set method has exponential complexity; improvements in computing efficiency by weak chains, regular chains, saturated chain were introduced[5]

Decomposing algebraic varieties

An application is an algorithm for solving systems of algebraic equations by means of characteristic sets. More precisely, given a finite subset F of polynomials, there is an algorithm to compute characteristic sets T1, ..., Te such that:

V(F) = W(T_1)\cup \cdots \cup W(T_e), \,

where W(Ti) is the difference of V(Ti) and V(hi), here hi is the product of initials of the polynomials in Ti.

See also

References

  1. ^ P. Aubry, D. Lazard, M. Moreno Maza (1999). On the theories of triangular sets. Journal of Symbolic Computation, 28(1–2):105–124
  2. ^ Hubert, E. Factorisation Free Decomposition Algorithms in Differential Algebra. Journal of Symbolic Computation, (May 2000): 641–662.
  3. ^ Maple (software) package diffalg.
  4. ^ Chou, Shang-Ching; Gao, Xiao Shan; Zhang, Jing Zhong. Machine proofs in geometry. World Scientific, 1994.
  5. ^ Chou S C, Gao X S; Ritt–Wu's decomposition algorithm and geometry theorem proving. Proc of CADE, 10 LNCS, #449, Berlin, Springer Verlag, 1990 207–220.

External links